package io.github.hadyang.leetcode.random;

import com.google.common.collect.Lists;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 分割回文串
 *
 * <p>给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
 *
 * <p>返回 s 所有可能的分割方案。
 *
 * <p>示例:
 *
 * <p>输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/palindrome-partitioning
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author haoyang.shi
 * @date 2019-10-19
 */
public class Q131 {
  public List<List<String>> partition(String str) {
    Set<List<String>> allSet = new HashSet<>();

    doPartition(allSet, new ArrayList<>(), str, 0);

    return new ArrayList<>(allSet);
  }

  private void doPartition(Set<List<String>> res, List<String> path, String string, int start) {
    if (start >= string.length()) {
      res.add(new ArrayList<>(path));
      return;
    }

    for (int i = start; i < string.length(); i++) {
      int size = path.size();
      String substring = string.substring(start, i + 1);
      if (!isHuiWen(substring)) {
        continue;
      }

      path.add(substring);

      doPartition(res, path, string, i + 1);
      path.remove(size);
    }
  }

  /**
   * aba / abba / a / aabbaa
   *
   * <p>aabbcc / ab
   *
   * @param string
   * @return
   */
  private boolean isHuiWen(String string) {
    char[] chars = string.toCharArray();
    if (chars.length == 0) {
      return false;
    }

    int i = 0, j = chars.length - 1;

    while (i <= j) {
      if (chars[i] != chars[j]) {
        return false;
      }

      i++;
      j--;
    }

    return true;
  }

  @Test
  public void testIsHuiWen() {
    List<String> strings = Lists.newArrayList("aba", "abba", "a", "aabbaa", "aabbcc", "ab", "efe");

    for (String string : strings) {
      System.out.println(string + ":" + isHuiWen(string));
    }
  }

  @Test
  public void testPartition() {
    List<String> strings = Lists.newArrayList("aba", "aab", "a", "ab", "efe");

    for (String string : strings) {
      System.out.println(string + ":" + partition(string));
    }
  }
}
